package leetbook.math;

import java.util.HashMap;

public class Solution166 {

    public static void main(String[] args) {
        Solution166 s = new Solution166();
        int a = -13, b = 3;
        System.out.println(a*1.0/b);
        System.out.println(s.fractionToDecimal(a,b));
    }

    public String fractionToDecimal(int numerator, int denominator) {
        int sign = (numerator<0)^(denominator<0)?-1:1; //记录符号
        long a = Math.abs((long)numerator), b = Math.abs((long)denominator); //方便取余，先求绝对值
        long gcd = gcd(a,b);
        //化简
        a /= gcd; b /= gcd;
        //整除
        if(b==1) return Long.toString(a*sign);
        //不能整除，就用一般的竖式除法做
        StringBuilder sb = new StringBuilder();
        //先添上符号部分、整数部分和小数点,计算余数部分
        sb.append(sign==-1?"-":"");sb.append(a/b);sb.append(".");
        //计算小数部分
        long res = a%b;
        HashMap<Long,Integer> resAndIdx = new HashMap<>();//记录余数和对应的小数点后第几位，方便找到循环起始
        while (res!=0){
            if(resAndIdx.containsKey(res)) break; //开始循环了
            resAndIdx.put(res,sb.length());
            res *= 10; //余数补0
            sb.append(res/b); //上商
            res %= b; //取余
        }
        //循环部分加括号
        if(res!=0){
            sb.insert(resAndIdx.get(res),"(");
            sb.append(")");
        }
        return sb.toString();
    }

    public long gcd(long a, long b){
        while (b!=0){
            long tmp = a%b;
            a = b;
            b = tmp;
        }
        return a;
    }
}
